# 超出时间限制:13

class Solution:
    """
    因为是寻找最大下标i和最大下标j，所以必须在后面完全有序的情况下，才会更新前面的一个字符
    而前面一个字符也只会与后序已有序字符串中比该字符小的字符交换，交换后仍保持有序，反转后即成为完全有序字符串的反转
    所以，将完全有序字符串的反转回有序字符串的步数在计算中是否重要

    由此，我们提出一种特殊的情况，所有字符完全逆序，称这种情况为“完全逆序”

    无重复值的完全逆序反转步数：
    basic_step[1] ba = 1步 = 1 : 1
    basic_step[2] cba = 5步 = 2 : 2+(2+1)*1
        cba -> cab = basic_step[1]
        cab -> bca = 1
        bca -> bac = basic_step[1]
        bac -> acb = 1
        acb -> abc = basic_step[1]
    basic_step[3] dcba = 23步 = 3 : 3+(3+1)*5
        dcba -> dabc = basic_step[2]
        dabc -> cdba = 1
        cdba -> cabd = basic_step[2]
        cabd -> bdca = 1
        bdca -> bacd = basic_step[2]
        bacd -> adcb = 1
        adcb -> abcd = basic_step[2]
    basic_step[4] edcba = 119步 = 4 : 4+(4+1)*23
    ......
    由此得出无重复值的完全逆序反转步数的递推通项公式：x[n]=n+(n+1)*x[n-1]

    有重复值相同的完全逆序反转步数：
    step[1.1] bba = 1+1 = 2步
        bba -> bab = basic_step[1]
        bab -> abb = 1
    step[1.2] baa = 1+1 = 2步
        baa -> aba = 1
        aba -> aab = basic_step[1]
    step[2.1] ccba = 5+1+2+1+2 = 11步
        ccba -> cabc = basic_step[2]
        cabc -> bcca = 1
        bcca -> bacc = step[1.1]
        bacc -> accb = 1
        accb -> abcc = step[1.1]
    step[2.2] cbba = 2+1+5+1+2 = 11步
        cbba -> cabb = step[1.1]
        cabb -> bcba = 1
        bcba -> babc = basic_step[2]
        babc -> acbb = 1
        acbb -> abbc = step[1.2]
    step[2.3] cbaa = 2+1+5+1+2 = 11步
        cbaa -> caab = step[1.2]
        cabb -> bcba = 1
        bcba -> babc = basic_step[2]
        babc -> acbb = 1
        acbb -> abbc = step[1.2]
    step[3.1] ddcba = 59步
    step[3.2] dccba = 11+1+23+1+11+1+11 = 59步
        dccba -> dabcc = step[2.1]
        dabcc -> cdcba = 1
        cdcba -> cabcd = basic_step[3]
        cabcd -> bdcca = 1
        bdcca -> baccd = step[2.2]
        baccd -> adccb = 1
        adccb -> abccd = step[2.2]
    ......

    由此得出一个推论（未证明）：当重复数量相同且重复分配形式相同时（例如ccba,cbba,cbaa），反转步数相同
    并由此假设得到存在一个相同字符的安全逆序反转步数的递推通项公式：y[n]=n+n*y[n-1]+x[n]

    step[2.5] bbaa = 2+1+2 = 5步
    bbaa -> baab = step[1.2]
    baab -> abba = 1
    abba -> aabb = step[1.1]

    【Demo】cdbea : 1+1+1+1+5+1+5+1+23+1+23 = 63步
        cdbea -> cdbae = basic_step[1] = 1
        cdbae -> cdaeb = 1
        cdaeb -> cdabe = basic_step[1] = 1
        cdabe -> cbeda = 1
        cbeda -> cbade = basic_step[2] = 5
        cbade -> caedb = 1
        caedb -> cabde = basic_step[2] = 5
        cabde -> bedca = 1
        bedca -> bacde = basic_step[3] = 23
        bacde -> aedcb = 1
        aedcb -> abcde = basic_step[3] = 23

    由此，进一步得到每向前推进一个字符的步骤：
    1. （前一步已完成）将该字符之后移动为有序
    2. 逐个计算从该字符替换到最小字符之间的步数，例如：
        basic_step[3] d->c->b->a
        step[2.5] b -> a
    """

    _MOD = 10 ** 9 + 7

    def __init__(self):
        # 定义完全逆序反转步数的缓存
        self.cache = {tuple([1]): 0}

        # 计算所有无重复值的完全逆序反转步数
        for i in range(1, 26):
            self.cache[(1,) * (i + 1)] = (i + (i + 1) * self.cache[(1,) * i]) % self._MOD

        # 添加存在一个相同字符的完全逆序翻转步数
        self.cache[(1, 2)] = 2

    def makeStringSorted(self, s: str) -> int:
        # 从后向前逐个处理字符
        ans = 0
        now = [0] * 26  # 记录当前字符数
        for ch in s[::-1]:
            i = ord(ch) - 97
            for j in range(i - 1, -1, -1):
                if now[j] > 0:
                    now[j] -= 1
                    now[i] += 1
                    ans += 1 + self.count(now) % self._MOD
                    now[j] += 1
                    now[i] -= 1
            # print("处理:", ch, now, "->", "结果:", ans)
            now[i] += 1

        print(s, ":", ans % self._MOD)
        return ans % self._MOD

    def count(self, now):
        """计算当前字符数的完全逆序"""
        # 按字母频数从小到大生成完全逆序的重复个数
        key = tuple(sorted(c for c in now if c > 0))

        if key not in self.cache:
            # 当只有两个字母时的公式：[n1,n2] -> (n1+n2)-1
            if len(key) == 2:
                return sum(key) - 1

            s = "".join(chr(122 - i) * key[i] for i in range(len(key)))
            self.cache[key] = self.makeStringSorted(s) % self._MOD
            # print(key, "(", s, ")", "=", self.cache[key])
        return self.cache[key]


if __name__ == "__main__":
    print(Solution().makeStringSorted("cba"))  # 5
    print(Solution().makeStringSorted("aabaa"))  # 2
    print(Solution().makeStringSorted("cdbea"))  # 63
    print(Solution().makeStringSorted("leetcodeleetcodeleetcode"))  # 982157772

    # 测试用例13
    # print(Solution().makeStringSorted("ppjsumufzmralrmefzicsbecynemkjjqnoxsjhbhpsqgyhstxlmwuhpxkd"))

    # 自制用例
    print(Solution().makeStringSorted("leetcode"))  # 4660
    print(Solution().makeStringSorted("leetcodeleetcode"))  # 624849580
